
//给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

//若可行，输出任意可行的结果。若不可行，返回空字符串。
public class 重构字符串 {
    public static void main(String[] args) {
        String S="aabbb";
        String s = reorganizeString(S);
        System.out.println(s);
    }
    public static String reorganizeString(String S) {
        if (S.length()<2)
            return S;
        //统计各个字符出现的次数
        int[] ints = new int[26];
        //记录出现次数最多的字符
        int max=0;
        //记录字符的索引
        int index=0;
        char[] chars = S.toCharArray();
        for (char c : chars) {
            ints[c-'a']++;
            if (ints[c-'a']>max){
                max=ints[c-'a'];
                index=c-'a';
            }
        }
        //如果出现次数最多的字符大于总字符个数的一半，则返回空格
        if (max>(S.length()+1)/2)
            return "";
        StringBuilder builder = new StringBuilder();
        //将最多的字符添加进去
       while (ints[index]>0){
           builder.append((char)(index+'a'));
           ints[index]--;
       }
        //将剩余字符依次插入
        int position=1;
        for (int i = 0; i < ints.length; i++) {
                while (ints[i]>0){
                    builder.insert(position,(char)(i+'a'));
                    ints[i]--;
                    position+=2;
                    //到末尾时，从头开始
                    if (position>builder.length())
                        position=1;
                }
        }
        return builder.toString();
    }
}
